package com.qz.sort;



/**
 * @Description 插入排序
 * @Author Flag
 * @Date: 2021/7/28 10:15
 * @Version: 1.0
 **/
public class InsertSortDome {
    public static void main(String[] args) {
//        int[] array = {101,34,119,1};
//        int[] array = {101,34,119,1,38,42,1111};
        int[] array = {1,2,3,4,5,6,7};
        int[] ints = insertSort8(array);

        for (int anInt : ints) {
            System.out.print(anInt+" ");
        }


    }

    /**
     * 插入排序
     * @param array 需要排序的集合
     * @return
     */
    public static int[] insertSort(int[] array){
//        //1.实例化一个数组，用来放排序后的结果
//        int[] result = new int[array.length];
//        //2.将待排序数组的第一个元素放入到排序后数组的第一个元素
//        result[0] = array[0];
//        //3.跳过第一个元素，遍历待排序数组的每一个元素
//
//       for (int i = 1 ; i < array.length - 1 ; i++) {
////            for (int j = 0; j < result.length - 1; j++) {
//
//           if (array[i] < result[i-1]){
//               leep:
//               for (int j = 0; j <= i; j++) {
//                   //4.判断当前元素和有序数组的位置关系
//                   if(array[i] < result[j]){
//                       int length = result.length - 1;
//                       //5.如果小于,有序数组元素后移，然后将该元素放到该位置
//                       while (i<=length){
//                           result[length]=result[length-1];
//                           length--;
//
//                       }
//                       result[j] = array[i];
//                       break leep;
//
//                   }
//               }
//           } else {
//               result[i] = array[i];
//           }
//
//
//        }
//        //6.如果大于，继续循环


        for (int i = 1; i < array.length; i++) {
            //定义一个待插入的数
            int insertValue = array[i];
            int insertIndex= i-1;
            //第一次{101,34,119,1}  ->34,101,119,1

            while (insertIndex >= 0 && insertValue < array[insertIndex]){
                array[insertIndex+1] = array[insertIndex];
                insertIndex -- ;
            }

            array[insertIndex+1 ] = insertValue;

        }
        return array;

    }


    /**
     * 插入排序--- 从小到大
     * 先说说思想:
     * 假定一个有序队列和一个无序队列，
     * 挨个遍历每一个无序队列的每一个元素，然后放到有序队列合适的位置
     *
     *
     * @param array
     * @return
     */
    public static int[] insertSort3(int[] array){
        //第一次
//        int[] arr = {101,34,119,1,38,42,1111};

        //拿到第一个元素
        int insertIndex = 1-1;
        int insertValue = array[1];
        while (insertIndex  >=  0  && array[insertIndex] > insertValue){
            array[insertIndex + 1] = array[insertIndex];
            insertIndex -- ;
        }
        array[insertIndex + 1] = insertValue;




        return array;
    }

    /**
     * 插入排序,从小到大
     *
     * 什么是插入排序？
     * 1.将数组分成两部分，一部分是有序的，一部分是无序的，
     * 2.将无序的部分，插入到有序的位置上，
     * 3.例如，以从小到大为例，找到一个元素，从后向前遍历
     *      找到大于当前元素的，继续往前找，同时数据需要移动
     *      找到小于当前元素的，停止遍历，将数据放到遍历元素的后一个位置
     *
     * @param array
     * @return
     */
    public static int[] insertSort4(int[] array){
//        int[] array = {101,34,119,1};
//        for (int i = 1; i < array.length; i++) {
            //34,101,119,1
        int insertValue = array[1];
        int insertIndex = 1-1 ;
//        int minValue = array[0];
            while (insertIndex >= 0 && insertValue < array[insertIndex]){
                array[insertIndex+1] = array[insertIndex];
                insertIndex--;
            }
            //交换位置
            array[insertIndex+1] = insertValue;
//        }



        return array;
    }


    /**
     * 插入排序，从小到大
     * @param array
     * @return
     */
    public static int[] insertSort5(int[] array){
        //insertValue用来存储需要插入的只
        int insertValue = array[1];
        for (int i = 1; i < array.length ; i++) {
            insertValue = array[i];
            //insertIndex用来存储拆入的坐标，因为第一次的时候，坐标是insertValue的前一个值，
            //其实insertIndex也是有序数组的最后一个元素的值
            int insertIndex= i-1;
            //1.insertIndex>=0表示不让下标越界
            //2.array[insertIndex] > insertValue，保证的是，让插入的数据一直小于当前游标指向的数据，因为这样的话，证明还找到合适的位置
            while(insertIndex >= 0 && array[insertIndex] > insertValue){
                //将舒服移动到后面，其实就是覆盖掉待插入的数据
                array[insertIndex+1] = array[insertIndex];
                //然后，将游标的数据向后移动
                insertIndex--;
            }
            //这里加一是因为，虽然找到了小于insertValue的值，但是不能放到当前位置上，需要放到后面
            array[insertIndex+1] = insertValue;
        }



        return array;
    }

    /**
     * 插入排序， 从小到大
     *
     * 数组分成两半，然后遍历后面每一个元素，直到找到位置
     *
     *
     * @param array
     * @return
     */
    public static int[] insertSort6(int[] array){

//        int[] array = {101,34,119,1,38,42,1111};
//        int value = array[1];
//        int insertIndex = 0;
//        int i = insertIndex;
//        for (; i >= 0; i--) {
//            if(value > array[i]){
//                break;
//            }
//            array[insertIndex+1] = array[insertIndex  ];
//        }
//
//        array[i+1] = value;
//

//        return array;


        for (int i = 0; i < array.length -1 ; i++) {
            int value = array[i+1];
            int insertIndex = i;
            int j = insertIndex;
            for (; j >= 0; j--) {
                if(value > array[j]){
                    break;
                }
                array[insertIndex+1] = array[insertIndex  ];
            }

            array[j+1] = value;
        }


        return array;

    }


    /**
     * 插入排序
     * 什么是插入排序，
     * 首先将数组分成两部分，一部分是有序的，一部分是无序的，
     * 然后遍历每一个无序的元素，将无序的元素加入到有序集合中的某个位置
     * 因为第一个元素，就他自己，所以默认是有序的，所以跳过第一个元素
     *
     * @param array
     * @return
     */
    public static int[] insertSort7(int[] array){
        /**
         * 第一论
         */
//        int insertValue = array[1];
//        int insertIndex= 0;
//        for (; insertIndex >=0 ; insertIndex--) {
//            if(array[insertIndex] < insertValue){
//                break;
//            }
//            array[insertIndex+1] = array[insertIndex];
//
//        }
//        array[insertIndex+1] = insertValue;


        /**
         * 第二论
         */


        int insertValue;
        int insertIndex;
        for (int i = 1; i < array.length; i++) {
            insertValue = array[i];
            insertIndex= i-1;
            for (; insertIndex >=0 ; insertIndex--) {
                if(array[insertIndex] < insertValue){
                    break;
                }
                array[insertIndex+1] = array[insertIndex];

            }
            array[insertIndex+1] = insertValue;
        }


        return array;
    }


    /**
     * 插入排序，数组分成两份，第一个作为有序看待，第二份作为无序看待，然后找到合适的位置
     * @param array
     * @return
     */
    public static int[] insertSort8(int[] array){
//        int insertValue = array[1];
//        int insertIndex= 1-1;
//        //保证下标不越界，并且，并且没有找到比插入值小的
//        while (insertIndex>=0 && array[insertIndex] > insertValue){
//            //元素后移
//            array[insertIndex+1] = array[insertIndex];
//            insertIndex--;
//        }
//        array[insertIndex+1] = insertValue;
        int insertValue;
        int insertIndex;
        for (int i = 1; i < array.length ; i++) {
            insertValue = array[i];
            insertIndex= i-1;
            //保证下标不越界，并且，并且没有找到比插入值小的
            while (insertIndex>=0 && array[insertIndex] > insertValue){
                //元素后移
                array[insertIndex+1] = array[insertIndex];
                insertIndex--;
            }
            array[insertIndex+1] = insertValue;

        }
        return array;
    }
}
